<html>
<head><meta charset="utf-8"><title>understanding data-flow analysis · t-compiler/wg-mir-opt · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/index.html">t-compiler/wg-mir-opt</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html">understanding data-flow analysis</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="215032012"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215032012" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215032012">(Oct 29 2020 at 21:39)</a>:</h4>
<p>I feel like the more I read about data-flow analysis the less I understand it <span aria-label="laughing" class="emoji emoji-1f606" role="img" title="laughing">:laughing:</span></p>
<p>Isn't it just iterating over all the statements and terminators and keeping track of some state at each one? Or is it more involved? Thanks!</p>



<a name="215032977"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215032977" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dániel Buga <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215032977">(Oct 29 2020 at 21:48)</a>:</h4>
<p>Sure, but program execution can also be thought of as "iterating over instructions and keeping track of some state" <span aria-label="smile" class="emoji emoji-1f642" role="img" title="smile">:smile:</span></p>
<p>As far as I can tell (and correct me if I'm wrong, I'm just trying to get into the topic myself), the point of DFA is to reason about a program and mine information that is useful for code transformations, without actually running it.</p>



<a name="215037704"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215037704" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215037704">(Oct 29 2020 at 22:41)</a>:</h4>
<p>I guess I wasn't very clear <span aria-label="smile" class="emoji emoji-1f642" role="img" title="smile">:smile:</span> When I said "keeping track of some state" I didn't mean executing the program, I meant e.g. what variables have been assigned to</p>



<a name="215037837"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215037837" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215037837">(Oct 29 2020 at 22:42)</a>:</h4>
<p>It keeps track of state, and propagates that state along control flow edges, until that state doesn't change anymore</p>



<a name="215037923"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215037923" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215037923">(Oct 29 2020 at 22:43)</a>:</h4>
<p>The thing that confuses me is how it works for branching: How does it keep track of all the possibilities depending on which branches were taken? E.g. how does it keep track of <code>a</code>'s init status?</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="k">fn</span> <span class="nf">function</span><span class="p">(</span><span class="n">x</span>: <span class="kt">bool</span><span class="p">,</span><span class="w"> </span><span class="n">y</span>: <span class="kt">bool</span><span class="p">)</span><span class="w"> </span>-&gt; <span class="kt">i32</span> <span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">a</span><span class="p">;</span><span class="w"></span>
<span class="w">    </span><span class="k">if</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="n">a</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="n">a</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">2</span><span class="p">;</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="w">    </span><span class="n">a</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>



<a name="215038099"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038099" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038099">(Oct 29 2020 at 22:45)</a>:</h4>
<p>When multiple control flow edges enter a block, the state they carry is unified. In this case that means <code>&amp;</code>-ing the "initialized" state of each variable.</p>



<a name="215038141"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038141" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038141">(Oct 29 2020 at 22:45)</a>:</h4>
<p>So <code>a</code> is initialized at the end of the function if <code>a</code> is initialized at the end of the <code>if</code> and <code>else</code> block</p>



<a name="215038235"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038235" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038235">(Oct 29 2020 at 22:46)</a>:</h4>
<p>Well, the <code>else</code> arm is missing, so there are actually 3 control flow edges that reach the last <code>a</code>, one of which doesn't initialize <code>a</code></p>



<a name="215038271"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038271" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038271">(Oct 29 2020 at 22:47)</a>:</h4>
<p>So does the pass branch out like the program?</p>



<a name="215038297"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038297" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038297">(Oct 29 2020 at 22:47)</a>:</h4>
<p>I.e. it follows each branch and then checks the results of each?</p>



<a name="215038371"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038371" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038371">(Oct 29 2020 at 22:48)</a>:</h4>
<p>I guess I understand now how it works for the init check, but I still feel confused about how it works for optimizations</p>



<a name="215038375"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038375" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038375">(Oct 29 2020 at 22:48)</a>:</h4>
<p>Yeah, it propagates the state through every block and edge</p>



<a name="215038388"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038388" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038388">(Oct 29 2020 at 22:48)</a>:</h4>
<p>Hmm, interesting</p>



<a name="215038396"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038396" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038396">(Oct 29 2020 at 22:48)</a>:</h4>
<p>This stuff is so cool <span aria-label="big smile" class="emoji emoji-1f604" role="img" title="big smile">:big_smile:</span></p>



<a name="215038407"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038407" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038407">(Oct 29 2020 at 22:48)</a>:</h4>
<p>Check out the <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/impls/struct.MaybeStorageLive.html"><code>MaybeStorageLive</code></a> impl, it's relatively simple and used in optimizations</p>



<a name="215038426"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038426" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038426">(Oct 29 2020 at 22:49)</a>:</h4>
<p>Great, thanks! I'll check it out :)</p>



<a name="215038509"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038509" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038509">(Oct 29 2020 at 22:50)</a>:</h4>
<p>I guess part of it is there's a lot of technical terminology that can be confusing</p>



<a name="215038540"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038540" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038540">(Oct 29 2020 at 22:50)</a>:</h4>
<p>Yeah, lots of mathematics</p>



<a name="215038553"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038553" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038553">(Oct 29 2020 at 22:50)</a>:</h4>
<p>because dataflow state is modeled as a lattice</p>



<a name="215038596"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038596" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038596">(Oct 29 2020 at 22:51)</a>:</h4>
<p>Yes, the lattice part confuses me. I tried to read the section in the Dragon Book that talks about this and it was over my head when I got to the "foundations of data-flow analysis" section</p>



<a name="215038657"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038657" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038657">(Oct 29 2020 at 22:52)</a>:</h4>
<p>I think I'll try to read that pass you mentioned and then try the Dragon Book again <span aria-label="smile" class="emoji emoji-1f642" role="img" title="smile">:smile:</span></p>



<a name="215038713"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038713" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038713">(Oct 29 2020 at 22:53)</a>:</h4>
<p>Actually it's a semilattice <a href="https://en.wikipedia.org/wiki/Semilattice">https://en.wikipedia.org/wiki/Semilattice</a></p>



<a name="215038739"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038739" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038739">(Oct 29 2020 at 22:53)</a>:</h4>
<p>Which makes sense – the "join" operation is exactly what happens when you have &gt;1 incoming control flow edge</p>



<a name="215038751"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038751" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038751">(Oct 29 2020 at 22:53)</a>:</h4>
<p><span aria-label="thinking" class="emoji emoji-1f914" role="img" title="thinking">:thinking:</span></p>



<a name="215038773"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038773" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038773">(Oct 29 2020 at 22:53)</a>:</h4>
<p>I think what confuses me is the combination of the semilattice and meet/join ops</p>



<a name="215038851"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038851" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038851">(Oct 29 2020 at 22:54)</a>:</h4>
<p>If the question you're trying to answer is "is this property <em>definitely</em> true for this local" this <em>join</em> operation will usually be <code>&amp;</code>, if the question is "<em>might</em> this property be true for this local", then the <em>join</em> operation will be <code>|</code></p>



<a name="215038865"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038865" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038865">(Oct 29 2020 at 22:55)</a>:</h4>
<p>Interesting.</p>



<a name="215038873"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038873" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038873">(Oct 29 2020 at 22:55)</a>:</h4>
<p>Does that make sense?</p>



<a name="215038892"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038892" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038892">(Oct 29 2020 at 22:55)</a>:</h4>
<p>Partially.</p>



<a name="215038894"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038894" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038894">(Oct 29 2020 at 22:55)</a>:</h4>
<p>Do you know of a less-mathematical explanation that I could read before I get to the full version with all the equations? Something that goes through the analysis like you're the computer</p>



<a name="215038913"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038913" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038913">(Oct 29 2020 at 22:55)</a>:</h4>
<p>Thanks for trying to explain this to me by the way :)</p>



<a name="215038915"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038915" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038915">(Oct 29 2020 at 22:55)</a>:</h4>
<p>Unfortunately not</p>



<a name="215038986"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215038986" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215038986">(Oct 29 2020 at 22:56)</a>:</h4>
<p>Maybe once I understand it I'll try to write something like that...</p>



<a name="215039019"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215039019" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215039019">(Oct 29 2020 at 22:56)</a>:</h4>
<p>I read <a href="http://smallcultfollowing.com/babysteps/blog/2017/03/25/unification-in-chalk-part-1/">niko's post about unification</a> which helped clear things up a lot, so I was wondering if there was something like that for data-flow</p>



<a name="215040870"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215040870" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215040870">(Oct 29 2020 at 23:16)</a>:</h4>
<p>In case anyone else is interested, I found this slide deck from CMU, though it's still pretty mathematical: <a href="http://www.cs.cmu.edu/afs/cs/academic/class/15745-s06/web/handouts/05.pdf">http://www.cs.cmu.edu/afs/cs/academic/class/15745-s06/web/handouts/05.pdf</a></p>



<a name="215041162"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215041162" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215041162">(Oct 29 2020 at 23:20)</a>:</h4>
<p>this series of videos is pretty approachable IIRC <a href="https://www.youtube.com/watch?v=NVBQSR_HdL0&amp;list=PL_sGR8T76Y58l3Gck3ZwIIHLWEmXrOLV_&amp;index=2">https://www.youtube.com/watch?v=NVBQSR_HdL0&amp;list=PL_sGR8T76Y58l3Gck3ZwIIHLWEmXrOLV_&amp;index=2</a></p>
<div class="youtube-video message_inline_image"><a data-id="NVBQSR_HdL0" href="https://www.youtube.com/watch?v=NVBQSR_HdL0&amp;list=PL_sGR8T76Y58l3Gck3ZwIIHLWEmXrOLV_&amp;index=2"><img src="https://i.ytimg.com/vi/NVBQSR_HdL0/default.jpg"></a></div>



<a name="215041191"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215041191" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215041191">(Oct 29 2020 at 23:20)</a>:</h4>
<p><span class="user-mention" data-user-id="307537">@Camelid</span> If you have a (e)library available, I'm fond of <a href="https://www.cs.rochester.edu/~scott/pragmatics/">https://www.cs.rochester.edu/~scott/pragmatics/</a> -- I found it more approachable than the dragon book.  (I have 3e in dead tree.)</p>



<a name="215041333"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215041333" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215041333">(Oct 29 2020 at 23:22)</a>:</h4>
<p>Thanks! I'll check out the videos and the book :)</p>



<a name="215041376"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215041376" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215041376">(Oct 29 2020 at 23:23)</a>:</h4>
<p>Side note: I think for some reason the most approachable part of the dragon book is in the middle, where they talk about three address code and other IRs. Not sure why <span aria-label="shrug" class="emoji emoji-1f937" role="img" title="shrug">:shrug:</span></p>



<a name="215041464"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215041464" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dániel Buga <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215041464">(Oct 29 2020 at 23:24)</a>:</h4>
<p>This is not part of the 5 video playlist, but it's from the same lecture series. A 20 minute video walking through an example: <a href="https://www.youtube.com/watch?v=jnbMirDEByY">https://www.youtube.com/watch?v=jnbMirDEByY</a></p>
<div class="youtube-video message_inline_image"><a data-id="jnbMirDEByY" href="https://www.youtube.com/watch?v=jnbMirDEByY"><img src="https://i.ytimg.com/vi/jnbMirDEByY/default.jpg"></a></div>



<a name="215041507"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215041507" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215041507">(Oct 29 2020 at 23:25)</a>:</h4>
<p>there's also an approachable chapter in Muchnick's book: its covers fundamentals, some of the mathematics, but also algorithms and pseudocode</p>



<a name="215041665"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215041665" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215041665">(Oct 29 2020 at 23:27)</a>:</h4>
<p>(the rest of the book is great and approachable as well)</p>



<a name="215041744"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215041744" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215041744">(Oct 29 2020 at 23:28)</a>:</h4>
<p>But yes, it's "just" iterating over everything and keeping state.  The interesting part is what to do for loops, and what order to visit basic blocks in.  For example, in <a href="https://github.com/rust-lang/rust/pull/46869/files#diff-48cfd8d23465df0fd4bf512c8a382a33cf215b8742b5a6f24cde53d348e47e14R93">this (never-finished) pass</a> I went in reverse-post-order and assumed the worst.  You can also just run to a fixpoint, at the cost of more effort.</p>



<a name="215041788"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215041788" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215041788">(Oct 29 2020 at 23:29)</a>:</h4>
<p><span class="user-mention" data-user-id="116113">@lqd</span> Thanks for the video! I started watching it and so far it looks very helpful :)</p>



<a name="215042551"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215042551" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215042551">(Oct 29 2020 at 23:42)</a>:</h4>
<p>I think I understand the meet/join operator now: It's just the set union operator, right?</p>



<a name="215042709"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215042709" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215042709">(Oct 29 2020 at 23:45)</a>:</h4>
<p>It can also be intersection, depending on the analysis</p>



<a name="215042924"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215042924" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215042924">(Oct 29 2020 at 23:49)</a>:</h4>
<p>Huh, okay. I just finished the first video; it was helpful because it took the approach of "being the computer" which I've always found to be helpful. I'll look through the liveness analysis pass that you mentioned to try to understand this in practice.</p>



<a name="215042926"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215042926" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215042926">(Oct 29 2020 at 23:49)</a>:</h4>
<p>Thanks again for the help!</p>



<a name="215049646"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215049646" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215049646">(Oct 30 2020 at 02:03)</a>:</h4>
<p>(Said otherwise, inside a Basic Block this stuff is all easy.  It's those darn edges that cause all the problems :P)</p>



<a name="215049737"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215049737" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215049737">(Oct 30 2020 at 02:05)</a>:</h4>
<p>And edges cause problems for human compilers too <span aria-label="wink" class="emoji emoji-1f609" role="img" title="wink">:wink:</span></p>



<a name="215536993"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215536993" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215536993">(Nov 04 2020 at 03:14)</a>:</h4>
<p><span class="user-mention silent" data-user-id="211727">Jonas Schievink</span> <a href="#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/understanding.20data-flow.20analysis/near/215038851">said</a>:</p>
<blockquote>
<p>If the question you're trying to answer is "is this property <em>definitely</em> true for this local" this <em>join</em> operation will usually be <code>&amp;</code>, if the question is "<em>might</em> this property be true for this local", then the <em>join</em> operation will be <code>|</code></p>
</blockquote>
<p>Now that I've watched more of the lecture series that <span class="user-mention silent" data-user-id="116113">lqd</span> recommended, I think I understand this. For example, you would use <code>&amp;</code> as the join operator if you were checking that a variable is initialized, since you need to know for sure. If you're trying to find all the possible values a variable can hold, you would use <code>|</code> as the join operator. Is that right?</p>



<a name="215537377"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/understanding%20data-flow%20analysis/near/215537377" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/understanding.20data-flow.20analysis.html#215537377">(Nov 04 2020 at 03:25)</a>:</h4>
<p>And IIUC, a "meet" semilattice uses the <code>&amp;</code> operator and a "join" semilattice uses the <code>|</code> operator?</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>